package io.github.hadyang.leetcode.bytedance;

/**
 * 相交链表
 *
 * <p>编写一个程序，找到两个单链表相交的起始节点。
 *
 * @author haoyang.shi
 */
public class Link1040 {

  public ListNode sortList(ListNode head) {
    ListNode midNode = findMid(head);

    return null;
  }

  private void sort(ListNode left, ListNode right, ListNode mid) {
    if (mid.next == left) {
      if (mid.val < right.val) {
        mid.next = right.next;
        right.next = mid;

        left.next = right;
      }

      return;
    } else {

    }

    return;
  }

  private ListNode findMid(ListNode head) {
    if (head.next == null) {
      return null;
    }

    ListNode slow = head, fast = head.next.next;

    while (fast != null) {
      slow = slow.next;

      if (fast.next == null) {
        return fast;
      }

      fast = fast.next.next;
    }

    return slow;
  }

  private static class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
      val = x;
    }

    @Override
    public String toString() {
      return "ListNode{" + "val=" + val + '}';
    }
  }

  public static void main(String[] args) {
    int[] ints = {4, 2, 1, 3};

    ListNode head = new ListNode(ints[0]);
    ListNode cur = head;
    for (int i = 1; i < ints.length; i++) {
      cur.next = new ListNode(ints[i]);
      cur = cur.next;
    }
    Link1040 main = new Link1040();
    ListNode res = main.sortList(head);

    while (res != null) {
      System.out.println(res.val);
      res = res.next;
    }
  }
}
